package _01_sort;

import org.junit.Test;

import java.util.Arrays;

import static _01_sort.SortUtil.swap;

/**
 * @author: mornd
 * @dateTime: 2023/6/23 - 0:42
 * 单边循环快排(洛穆托分区)
 * 1、选择最右侧元素作为基准点
 * 2、j找比基准点小的，i找比基准点大的，一旦找到，二者进行交换
 * 3、最后基准点与i交换，i即为基准点最终索引
 */
public class QuickSortLomuto {
    @Test
    public void test() {
        int[] arr = {8, 2, 7, 18, 53, 50, 68, 1, 9, 4, 10};
        quick(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    private void quick(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        // p 是基准点的下标，该下标的元素位置已经确定，下轮递归需要排除
        int p = partition(arr, left, right);
        quick(arr, left, p - 1);
        quick(arr, p + 1, right);
    }

    /**
     * 分区
     * 选择最右侧元素作为基准点
     * j找比基准点小的，i找比基准点大的，一旦找到，二者进行交换
     * 最后基准点与i交换，i即为基准点最终索引
     *
     * @param arr
     * @param left
     * @param right
     * @return 基准点索引，这里选用最右侧作为基准点
     */
    private int partition(int[] arr, int left, int right) {
        int pv = arr[right];
        int i = left;
        int j = left;
        while (j < right) {
            // j找到比基准点小的元素了
            if (arr[j] < pv) {
                // 并且i，j不在一起时
                if (i != j) {
                    swap(arr, i, j);
                }
                i++;
            }
            j++;
        }
        swap(arr, i, right);
        return i;
    }
}
